#include "Dfa.h"

template <class DataType>
Dfa<DataType>::Dfa()
{
}

template<class DataType>
Dfa<DataType>::Dfa(const DataType &startState, set<Transition<DataType> > &transition, set<DataType> &finalState)
{
	for(set<Transition<DataType> >::iterator it = transition.begin(); it != transition.end(); it++)
	{
		Transition<DataType> trans = *it;
		states.insert(trans.getFromState());
		states.insert(trans.getToState());
		symbols.insert(trans.getSymbol());
		transitions.insert(trans);
	}
	startStates.insert(startState);
	
	for (set<DataType>::iterator it = finalState.begin(); it != finalState.end(); it++) 
	{
		string end = *it;
		if (states.find(end) != states.end()) 
		{
			finalStates.insert(end);
		} 
	}
}

template <class DataType>
Dfa<DataType>::~Dfa()
{
}

template <class DataType>
set<DataType> Dfa<DataType>::getLanguage(int maxSteps)
{
	set<string>::iterator it = startStates.begin();
	string startState = *it;
	//set<DataType> result;
	getWords(maxSteps, startState, "", result);
	return result;
}

template <class DataType>
void Dfa<DataType>::getWords(int maxSteps, DataType &state, const string &word, set<DataType> &result){
	for(set<char>::iterator it = symbols.begin(); it != symbols.end(); it++)
	{
		set<DataType> possibleStates = getStates(state, *it);
		for(set<DataType>::iterator iter = possibleStates.begin(); iter != possibleStates.end(); iter++)
		{
			DataType state = *iter;
			string thisWord = word+*it;
			if(isEndState(state))
			{
				result.insert(thisWord);
			}
			if(thisWord.length() < maxSteps)
				{
					getWords(maxSteps, state, thisWord, result);
				
			}
		}
	}
}

template <class DataType>
set<DataType> Dfa<DataType>::getStates(const DataType &fromState, const char &symbol)
{
	Transition<DataType> lowerKey = Transition<DataType>(fromState, symbol, *states.begin());
	Transition<DataType> upperKey = Transition<DataType>(fromState, symbol, *states.rbegin());
	set<Transition<DataType> >::iterator iter = transitions.lower_bound(lowerKey);
	set<Transition<DataType> >::iterator end = transitions.upper_bound(upperKey);
	set<DataType> result;
	for (; iter != end; iter++) {
		Transition<DataType> transition = *iter;
		result.insert(transition.getToState());
	}
	
	return result;
}


template <class DataType>
bool Dfa<DataType>::isEndState(const DataType &state)
{
	return finalStates.find(state) != finalStates.end();
}

template<class DataType>
bool Dfa<DataType>::acceptString(const string &word)
{
	for(set<DataType>::iterator iter = result.begin(); iter != result.end(); iter++)
		{
		if(*iter == word) {
			return true;
		}
	}	
	return false;
}

template <class DataType>
ostream& operator <<(ostream& os, const set<string> &exp) {
	copy(exp.begin(), exp.end(), ostream_iterator<const string>(os, " | "));
	return os;
}